package model;

public class LCS_divide_conquer {

    /**
 * This method comput the longuest common subsequence between a and b by using 
 * the divide and conquer algorithm. 
 * @param a the first sequence
 * @param b the second sequence
 * @return The longuest common subsequence between a and b
 */
    public static String lcs(String a, String b) {
        int aLen = a.length();
        int bLen = b.length();
        int q = 0;
        //System.out.println("alen: "+aLen+" blen="+bLen);
        if (aLen <= 2 || bLen <= 2) {
            return LCS_dynamic.lcs(a, b);
        } else {
            int bMid = bLen / 2;
            int[] c = spaceEfficientLCSLength(a, b.substring(0, bMid));
            int[] g = backwardSpaceEfficientLCSLength(a, b.substring(bMid , bLen));
            int max = -1;
            
            int i;
            //Now we try to merge the results and find one caracter of the lcs
            for (i = 0; i < aLen; i++) {
                //System.out.println("c["+i+"]= "+c[i]+" g["+i+"]= "+g[i]);
                int somme = c[i] + g[i];
                if(c[i]==0)
                if (somme >= max) {
                    max = somme;
                    q = max==c[i]?i-1:i;
                }else{
                    
                }
                else if(g[i]==0){
                    if (somme > max) {
                    max = somme;
                    q = max==c[i]?i-1:i;
                }
                }
                else{
                    if (somme >= max) {
                    max = somme;
                    q = i;
                    }
                }
                /*if(c[i]==0 || g[i]==0)
                if (somme >= max) {
                    max = somme;
                    q = max==c[i]?i-1:i;
                }else {
                    
                }
                else{
                    if (somme > max) {
                    max = somme;
                    q = i;
                    }
                }*/
                
            }
            if(max==0)return "";
            
            //System.out.println("q: " + q + " LCS_TMP:" + a.charAt(q));
            String x1 = a.substring(0, q);
            String x2 = a.substring(q+1 , aLen);
            String y1 = b.substring(0, bMid);
            String y2 = b.substring(bMid , bLen);
            //System.out.println("x1= " + x1 + " x2= " + x2 + " y1=" + y1 + " y2=" + y2);
            /*if(q==0){
                return a.charAt(q) + lcs(x2, y2);
            }
            if(q==aLen){
                return lcs(x1, y1) + a.charAt(q);
            }*/
            return lcs(x1, y1) + a.charAt(q) + lcs(x2, y2);
        }


    }
    
/**
 * This method compute the length of the longuest common susequence between x and 
 * y by bottom-up technique
 * @param x first sequence
 * @param y second sequence
 * @return lengths of the common subsequences between y and subStrings of x 
 */
    private static int[] backwardSpaceEfficientLCSLength(String x, String y) {
        int xLength = x.length();
        int yLength = y.length();
        //System.out.println("backwardspaceEfficient btw: "+x+"\t"+y);
        int[] resultat = new int[xLength+1];
        int[][] matrice = new int[xLength + 1][yLength + 1];
        int i, j;
        //System.out.println("backwardspaceEfficient btw: "+x+"\t"+y);
        x=x+" ";
        y=y+" ";
        for (i = xLength; i >= 0; i--) {
            for (j = yLength; j >= 0; j--) {
                if (i == xLength) {
                    matrice[i][j] = 0;
                    resultat[i] = matrice[i][j];
                    continue;
                }
                if (j == yLength) {
                    matrice[i][j] = 0;
                    continue;
                }
                int cpt = 0;
                //System.out.println(x.charAt(i)+" == "+y.charAt(j));
                if (x.charAt(i) == y.charAt(j)) {
                    cpt = 1;
                }
                int tmp;
                tmp = Math.max(matrice[i][j + 1], matrice[i + 1][j]);
                matrice[i][j] = Math.max(tmp, matrice[i + 1][j + 1] + cpt);
                //System.out.println("c["+i+","+j+"]="+matrice[i][j]);
                if (j == 0) {
                    resultat[i] = matrice[i][j];
                }
            }
        }

        return resultat;

        // TODO Auto-generated method stub

    }
/**
 * This method compute the length of the longuest common susequence between x and 
 * y by top-down technique
 * @param x
 * @param y
 * @return engths of the common subsequences between y and subStrings of x
 */
    private static int[] spaceEfficientLCSLength(String x, String y) {
        int xLength = x.length();
        int yLength = y.length();
        int[] resultat = new int[xLength+1];
        int[][] matrice = new int[xLength + 1][yLength + 1];
        int i, j;
        //System.out.println("spaceEfficient btw: "+x+"\t"+y);
        x = " " + x;
        y = " " + y;
        for (i = 0; i <= xLength; i++) {
            for (j = 0; j <= yLength; j++) {
                if (i == 0) {
                    matrice[i][j] = 0;
                    continue;
                }
                if (j == 0) {
                    matrice[i][j] = 0;
                    resultat[i] = matrice[i][j];
                    continue;
                }
                int cpt = 0;
                if (x.charAt(i) == y.charAt(j)) {
                    cpt = 1;
                }
                int tmp;
                tmp = Math.max(matrice[i][j - 1], matrice[i - 1][j]);
                matrice[i][j] = Math.max(tmp, matrice[i - 1][j - 1] + cpt);
                //System.out.println("g["+i+","+j+"]="+matrice[i][j]);
                if (j == yLength) {
                    resultat[i] = matrice[i][j];
                    //System.out.println("resultat[" + String.valueOf(i - 1) + "]= " + resultat[j]);
                }
            }
        }

        return resultat;
    }

}
